package org.leetcode.middle.leetcode148;

import org.algorithm.List.ListNode;


public class Solution2 {
    public ListNode sortList(ListNode head) {
        return split(head,null);
    }

    // left=[head,mid) right =[mid,tail);
    private ListNode split(ListNode head,ListNode tail){
        if (head==null){
            return head;
        }

        if (head.next==tail){
            //断开不属于这部分的连接，并且tail不在这部分中
            head.next=null;
            return head;
        }

        ListNode slow = head;
        ListNode fast = head;

        //找到链表的中点，让快指针走两步，慢指针走一步，当快指针走到结尾时，慢指针的位置在链表中间
        while (fast!=tail){
            slow=slow.next;
            fast=fast.next;
            if (fast!=tail){
                fast=fast.next;
            }
        }
        ListNode mid = slow;

        ListNode left = split(head,mid);
        ListNode right = split(mid,tail);

        return merge(left,right);
    }
    private ListNode merge(ListNode left,ListNode right){
        ListNode dummy = new ListNode(-1);

        ListNode sortedList = dummy;

        while (left!=null && right!=null){
            if (left.val<right.val){
                sortedList.next=left;
                left=left.next;
            }else {
                sortedList.next=right;
                right=right.next;
            }

            sortedList=sortedList.next;
        }

        if (left==null){
            sortedList.next=right;
        }
        if (right==null){
            sortedList.next=left;
        }

        return dummy.next;
    }

}
